import pandas as pd
import numpy as np
import random, operator
import matplotlib.pyplot as plt

class City(object):
    """城市"""
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def distance(self, city):
        # 计算两个城市的距离,使用欧拉距离，也就是两个坐标的直线距离
        dx = abs(self.x - city.x)
        dy = abs(self.y - city.y)
        return np.sqrt((dx ** 2) + (dy ** 2))

    def __repr__(self):
        return "({},{})".format(self.x, self.y)

def generate_city(n):
    # 用于生成随机城市，返回两种形式的表达
    city_list = []  # 一种是城市坐标列表
    distances_array = [] # 一种是城市与城市间的距离矩阵
    for i in range(n):
        city_list.append(City(
            x=int(random.random() * 200),
            y=int(random.random() * 200)))
    for i in range(n):
        row = list()
        for j in range(n):
            row.append(np.linalg.norm(
                city_list[i].distance(city_list[j])))
        distances_array.append(row)
    distances_array = np.array(distances_array)
    return city_list, distances_array

class GeneticAlgorithm(object):
    """遗传算法解决旅行者问题"""
    def __init__(self, city_list, population_size,
        elite_size, mutation_rate, generations):
        self.city_list = city_list # 城市列表
        self.population_size = population_size # 种群大小
        self.elite_size = elite_size # 精英模式数量
        self.mutation_rate = mutation_rate # 变异的概率
        self.generations = generations # 进化的总代数
        self.progress = [] # 记录每一代的最优结果

    def init_population(self):
        # 创建一个种群
        population = []
        for i in range(self.population_size):
            route = random.sample(self.city_list, len(self.city_list))
            population.append(route)
        return population

    def fitness(self, route):
        # 计算个体的适应能力值
        path_distance = 0 # 路径的总距离
        for i in range(0, len(route)):
            from_city = route[i]
            if i + 1 < len(route):
                to_city = route[i + 1]
            else:
                to_city = route[0]
            path_distance += from_city.distance(to_city)
        distance = path_distance
        # 距离越长，适应能力值越小，因此用路径长度的倒数作为适应能力值
        return 1 / float(distance)

    def rank_routes(self, population):
        # 适应能力值排名
        fitness_results = {}
        for i in range(0, len(population)):
            fitness_results[i] = self.fitness(population[i])
        return sorted(fitness_results.items(), key = operator.itemgetter(1), reverse = True)

    def selection(self, population, population_ranked):
        # 根据适应能力值挑选个体进入杂交处理
        mating_pool = []  # 记录被挑选的个体
        df = pd.DataFrame(np.array(population_ranked), columns=["Index", "Fitness"])
        # 通过这个方法，把适应能力值归一化后，变成一个按排名的分数
        df['cum_sum'] = df.Fitness.cumsum()
        df['cum_perc'] = 100 * df.cum_sum / df.Fitness.sum()
        for i in range(0, self.elite_size):
            # 精英模式
            mating_pool.append(population[population_ranked[i][0]])
        for i in range(0, len(population_ranked) - self.elite_size):
            # 剩下的按轮盘赌选择
            pick = 100 * random.random() # 每次生成一个（0到1）随机数
            for i in range(0, len(population_ranked)):
                if pick <= df.iat[i, 3]: # 看落在那个区间，选择该个体
                    mating_pool.append(population[population_ranked[i][0]])
                    break
        return mating_pool

    def breed_population(self, mating_pool):
        # 杂交处理
        def breed(parent1, parent2):
            # 父母杂交，创建新的一代
            child_p1 = [] # 来自parent1的基因
            child_p2 = [] # 来自parent2的基因
            gene_A = int(random.random() * len(parent1))
            gene_B = int(random.random() * len(parent1))
            start_gene = min(gene_A, gene_B)
            end_gene = max(gene_A, gene_B)
            # 随机抽取parent1一段基因
            for i in range(start_gene, end_gene):
                child_p1.append(parent1[i])
            for item in parent2:
                # 剩下的都来自parent2
                if item not in child_p1:
                    child_p2.append(item)
            child = child_p1 + child_p2
            return child

        children = [] # 记录下一代个体
        length = len(mating_pool) - self.elite_size
        pool = random.sample(mating_pool, len(mating_pool)) # 打乱顺序
        for i in range(0, self.elite_size):
            # 精英模式，直接进入下一代
            children.append(mating_pool[i])
        for i in range(0, length):
            child = breed(pool[i], pool[len(mating_pool) - i - 1])
            children.append(child)
        return children

    def mutate_population(self, population):
        # 基因突变处理
        def mutate(individual):
            for index_city1 in range(len(individual)):
                if (random.random() < self.mutation_rate):
                    # 若个体（路径）发生变异，随机挑选两个城市交换位置
                    index_city2 = int(random.random() * len(individual))
                    city1 = individual[index_city1]
                    city2 = individual[index_city2]
                    individual[index_city1] = city2
                    individual[index_city2] = city1
            return individual

        mutated_population = []
        for index_population in range(0, len(population)):
            mutated_population.append(mutate(population[index_population]))
        return mutated_population

    def next_generation(self, current_generation):
        # 生成下一代
        population_ranked = self.rank_routes(current_generation) # 计算排名
        mating_pool = self.selection(current_generation, population_ranked) # 挑选个体繁衍
        children = self.breed_population(mating_pool) # 杂交处理
        new_generation = self.mutate_population(children) # 基因突变处理
        return new_generation # 最后返回新的一代种群

    def run(self):
        # 算法调用的入口
        population = self.init_population()
        self.progress.append(1 / self.rank_routes(population)[0][1])
        print("第一代最短路径: " + str(self.progress[0]))
        for i in range(0, self.generations):
            population = self.next_generation(population)
            self.progress.append(1 / self.rank_routes(population)[0][1])
        print("最后一代最短路径: " + str(1 / self.rank_routes(population)[0][1]))
        index_best_route = self.rank_routes(population)[0][0]
        return population[index_best_route]

    def draw_progress(self):
        plt.plot(self.progress)
        plt.ylabel('Distance')
        plt.xlabel('Generation')
        plt.show()

if __name__ == '__main__':
    citys, arr = generate_city(3)
    print(citys)
    print(arr)
    ga = GeneticAlgorithm(city_list=citys, population_size=50, elite_size=5, mutation_rate=0.01, generations=30)
    result = ga.run()
    ga.draw_progress()